package edu.bu.cs511.p5;

import java.util.LinkedList;
import java.util.Iterator;

/**
 * GenericScheduler A prototype scheduler including much of the main
 * scheduler functionality.  Methods are to be overridden and
 * specialized as needed.  This is basically a round robin scheduler
 * as is.  This method follows the Template Design Pattern and is
 * meant to be overridden by subclasses such as FPScheduler and
 * ProportionalScheduler.  Currently, this logic is for a RRScheduler.
 * One should be able to addTasks to the scheduler, as well as
 * removeTasks, and once added, tasks will be scheduled accordingly.<p/>
 *
 * A warning against PriorityQueues: Though you are guaranteed to
 * get the value with the highest priority from the queue, no
 * guarantees are made concerning the order of tasks of the same
 * priority.  This can lead to starvation EASILY.  I would stay
 * away from the java provided priority queues for this purpose
 * for that reason.  Thus why the insertRunQueue method exists, to
 * implement our own controlled methodology for insertions.
 * <p/>
 * Can remove the synchonized from the methods and attach it to datastructures
 * if there are scalability issues.
 * <p/>
 * 2/16/06, Gabriel Parmer: generalized from RRScheduler 4/10/06
 */
public class GenericScheduler implements IScheduler {
    /* the maximum concurrency allowed to this scheduler, default 1000 */
    private int maxConcurrency = 1000;

    /** 
     * RI: each task scheduled by this scheduler must be in one of
     * runQueue, currentlyRunning, or waitingList, and exactly one and
     * for each task t, t.getAllocatedConcurrency() <= maxConcurrency
     * and the concurrency of all tasks in the waitingList should be
     * 0.  <p/>
     *
     * AF(c) = [t1, t2, ... , tn] where ti is a task scheduled by this
     * scheduler and ti.concurrency is the concurrency currently
     * allocated to that task.
     */
    public boolean repOk() {
	int concurr = 0;

	for (Task cur : runQueue) {
	    concurr += cur.schedData.getAllocatedConcurrency();
	}
	for (Task cur : waitingList) {
	    concurr += cur.schedData.getAllocatedConcurrency();
	}
	for (Task cur : currentlyRunning) {
	    concurr += cur.schedData.getAllocatedConcurrency();
	}
	if (concurr > maxConcurrency) 
	    return false;
	
	for (Task cur : runQueue) if (!repHelper(cur)) return false;
	for (Task cur : waitingList) if (!repHelper(cur)) return false;
	for (Task cur : currentlyRunning) if (!repHelper(cur)) return false;
	
	for (Task cur : waitingList) if (cur.schedData.getAllocatedConcurrency() != 0) return false;
	
        return true;
    }

    /**
     * See if a task appears more than once in the data structures.<p/>
     *
     * @REQUIRES t is the task which we should look through all the
     * queues for. <p/>
     *
     * @EFFECTS return true if t appears more than once in all of
     * the queues, or false otherwise
     */
    private boolean repHelper(Task t)
    {
	int count = 0;

	for (Task cur : runQueue) if (cur == t) count++;
	for (Task cur : waitingList) if (cur == t) count++;
	for (Task cur : currentlyRunning) if (cur == t) count++;

	if (count > 1) return false;
	return true;
    }

    /**
     * Insert a task into the runqueue.<p/>
     *
     * @REQUIRES t is the task to be insert into the runQueue.
     * <p/>
     * @MODIFIES runQueue is modified in that t is added to it in a
     * manner defined by extending classes.  For this class, it is
     * added to the end of the runqueue.
     */
    protected void insertRunQueue(Task t) {
        runQueue.addLast(t);
        return;
    }

    /**
     * Queue of tasks that are READY to execute, ie. they have not
     * expended their desired concurrency.  Protected so that the
     * insertRunQueue method can be overridden.
     */
    protected LinkedList<Task> runQueue;

    /**
     * Tasks that are currently running and have expended
     * concurrency
     */
    protected LinkedList<Task> currentlyRunning;

    /**
     * Tasks that cannot run now (are not enabled).  Concurrency for these tasks
     * should be 0.
     */
    protected LinkedList<Task> waitingList;

    /**
     * Constructor which creates a GenericScheduler
     * <p/>
     * @REQUIRES none
     */
    public GenericScheduler() {
        runQueue = new LinkedList<Task>();
        currentlyRunning = new LinkedList<Task>();
        waitingList = new LinkedList<Task>();
    }

    /**
     * Constructor to create a proportional share scheduler with a
     * defined maximum concurrency level (maximum number of threads it
     * will every ask for). <p/>
     * 
     * @REQUIRES maxConcurr is the maximum value for the concurrency
     * supported by this scheduler, or the maximum number of threads it will
     * pass to children.
     */
    public GenericScheduler(int maxConcurr) {
        this();
        maxConcurrency = maxConcurr;
    }

    /**
     * Add a new task to this scheduler's structures.  Specify a
     * proportion that task is to have.<p/>
     *
     * @REQUIRES t is the task to be added to the scheduler's
     * queues. s is ignored.<p/>
     *
     * @MODIFIES adds the task to the waitingList of this scheduler.
     * <p/>
     * 
     * @EFFECTS return true if the task was successfully added, false if
     * not.
     */
    synchronized public boolean addTask(Task t, String s) {
        addTask(t);
        return true;
    }

    /**
     * Add a new task to this scheduler's structures.  Specify a
     * proportion that task is to have.<p/>
     *
     * @MODIFIES add the task t to the waitingList of this scheduler.
     * <p/>
     * @REQUIRES t is a Task that is not a ThreadManager
     * <p/>
     * @EFFECTS return true if the task was successfully added, false if
     * not.
     */
    synchronized public boolean addTask(Task t) {
        SchedData sd = new SchedData();
        t.schedData = sd;
        waitingList.add(t);

        return true;
    }

    /**
     * Remove a given task from the scheduler's structures.  If the
     * task is not in any of the queues, then a bug report is emitted.<p/>
     *
     * @REQUIRES task t must be in either the runQueue, the
     * waitingList, or the currentlyRunning for this scheduler.
     *
     * <p/>
     * @MODIFIES remove the task t from the runQueue or the waitingList.
     */
    synchronized public void removeTask(Task t) {
        if (removeFromRunQueue(t) != -1) return;
        if (waitingList.remove(t)) return;
        if (currentlyRunning.remove(t)) return;

        System.out.println("BUG in edu.bu.cs511.p5.GenericScheduler: attempted to remove task not in taskQueues.");
    }

    /**
     * The generic scheduler does not need an initString.
     */
    public void initString(String s) {
    }

    /** 
     * Terminate this scheduler by deallocating all of its data and
     * informing any tasks as needed. <p/>
     *
     * @MODIFIES Deallocates all datastructures associated with this
     * scheduler.
     */
    synchronized public void terminateScheduler() {
        /*
	 * FIXME: Delete all private data...I should do this right as
         * this is a memory leak.
	 */
        runQueue = null;
        waitingList = null;
        currentlyRunning = null;
    }

    /**
     * Make a scheduling decision.  This will include choosing a
     * single task which is to execute next out of all tasks the
     * scheduler is tracking.<p/>
     *
     * @REQUIRES there are tasks in the runQueue, thus the concurrency
     * > 1.  <p/>
     *
     * @MODIFIES Schedule tasks in round-robin order.  Manipulate the task
     * queues. <p/>
     *
     * @EFFECTS return the task that should be run next.  null if
     * there was a race condition between the concurrency value and
     * the deletion of a task.  null should be taken to mean "there is
     * nothing to schedule".
     */
    synchronized public Task schedule() {
        Task t;

        if (runQueue.size() == 0) {
            //System.out.println("BUG: scheduler asked to schedule when there are no " +
            //        "tasks in it's runqueue.");
            return null;
        }

	/* leave it in the queue */
        t = runQueue.peek();
        SchedData sd = (SchedData) t.schedData;
        sd.setAllocatedConcurrency(sd.getAllocatedConcurrency() + 1);

        // only if this task has no more concurrency will we put it in
        // the currently running queue.
        if (sd.getAllocatedConcurrency() == sd.getRequestedConcurrency()) {
            // FIXME: This might throw an exception in which case we
            // have a bug.  Perhaps kill this scheduler and all its
            // tasks.
	    /* remove the task from the runqueue, it has no more concurrency!*/
            t = runQueue.poll();

	    /* and add it to the currently running queue */
            currentlyRunning.add(t);
        }

        return t;
    }

    /**
     * Remove the task from the runqueue.<p/>
     *
     * @REQUIRES Task t is the task to be removed from the runQueue.
     * <p/>
     * @EFFECTS return the concurrency level or -1 if the element doesn't
     * exist in the runQueue.
     * <p/>
     * @MODIFIES removes t from the runQueue if it is on it.
     */
    private int removeFromRunQueue(Task t) {
        SchedData sd = (SchedData) t.schedData;
        int concur = sd.getRequestedConcurrency();

        if (runQueue.remove(t)) return concur;

        return -1;
    }

    /**
     * Add a task to the runqueue.<p/>
     *
     * @MODIFIES runQueue, adds task at end of queue
     *
     * @REQUIRES t is the task to be inserted into the runqueue.
     */
    protected void addToRunqueue(Task t) {
        //        runQueue.addLast(an);
        insertRunQueue(t);
    }

    /**
     * This method is invoked by the SchedTask owning this scheduler
     * every time that the task which this scheduler told it to
     * execute (returned from scheduler) has finished executing,
     * ie. the job finished.  This method is used to clean up and
     * update state.<p/>
     *
     * @REQUIRES t must be scheduled by this scheduler and is in the
     * currentlyRunning queue and has just finished executing; blocked
     * is true if it cannot compute further at this time (ie. it is
     * blocked). <p/>
     *
     * @MODIFIES if the task t is blocked, take it out of the runqueue
     * and put it in the waitingList.
     */
    synchronized public void jobFinished(Task t, boolean blocked) {

	//System.out.println(t.getName()+" has requested concurrency of "+ t.schedData.getRequestedConcurrency());

        /* this scheduler has been deleted...return and exit out */
        if (runQueue == null || currentlyRunning == null) return;
        if (!runQueue.remove(t) && !currentlyRunning.remove(t)) {
            /* Must have been removed while running, we're done here! */
            //System.out.println("BUG in edu.bu.cs511.p5.GenericScheduler: finshed job not in runQueue or currentlyRunning.");
            return;
        }

        t.schedData.setAllocatedConcurrency(t.schedData.getAllocatedConcurrency() - 1);

	/* 
	 * Assumes that OpcodeTask are not multithreaded thus only
	 * request concurrency of 1...should be the same as if
	 * (t.schedData.getAllocatedConcurrency() < 1)
	 */
        if (blocked) {
            waitingList.add(t);
        } else {
            addToRunqueue(t);
        }
    }

    /**
     * Update the concurrency given a child and its new concurrency,
     * and return the concurrency requested by this scheduler.<p/>
     *
     * @MODIFIES Change the concurrency of child in list to concurrency if child
     * is in list.
     * <p/>
     * @EFFECTS return the sum of the concurrencies of all tasks in the
     * specified list.
     * <p/>
     * @REQUIRES A list iterator to the list you want to update the
     * concurrency of, the child task that has a new updated concurrency, and
     * the concurrency value to update the child to.
     */
    private int updateConcurrency(Iterator<Task> it, Task child, int concurrency) {
        int concurSum = 0;

        while (it.hasNext()) {
            Task t = it.next();
            SchedData sd = (SchedData) t.schedData;

            /* remember, child might be null */
            if (t.equals(child)) {
                sd.setRequestedConcurrency(concurrency);
            }

            concurSum += sd.getRequestedConcurrency();
        }

        //System.out.println(concurSum);

        return concurSum;
    }

    /**
     * Compute the current concurrency level observed at this
     * scheduler (ie. the the minimum of number of threads that have
     * been requested by this scheduler's children and the maximum
     * allowable concurrency for this scheduler.)  <p/>
     *
     * @REQUIRES child might be null, concurrency is the concurrency of the
     * child. <p/>
     *
     * @EFFECTS return the currently observed concurrency which is the
     * minimum of sum of the requested concurrency of each child, and
     * the maximum allowable concurrency at this scheduler.  This will
     * change as opcodes are enabled (increase), and as they run
     * (decrease).
     */
    synchronized public int setChildConcurrencyLevel(Task child, int concurrency) {
        int location; // FIXME: unused
        int concurSum = 0;

        /**
         * If this child is in the waitingList, then remove it and add
         * it to the runQueue.
         */
        if (child != null && waitingList.remove(child)) {
            SchedData sd = (SchedData) child.schedData;
            sd.setRequestedConcurrency(concurrency);
            insertRunQueue(child);
        }

        /**
         * Update the child's concurrency level and return our new
         * concurrency level.
         */
        Iterator<Task> li = runQueue.iterator();
        concurSum += updateConcurrency(li, child, concurrency);
        li = currentlyRunning.iterator();
        concurSum += updateConcurrency(li, child, concurrency);

        //System.out.println(Math.min(concurSum, maxConcurrency));

        return Math.min(concurSum, maxConcurrency);
    }

    /**
     * Get the concurrency level of a specific child.<p/>
     *
     * @REQUIRES child is the task to get the concurrency of.<p/>
     *
     * @EFFECTS is the concurrency level of child.
     */
    public int getChildConcurrencyLevel(Task child)
    {
	return ((SchedData)child.schedData).getRequestedConcurrency();
    }
    
    /**
     * Simply for use to recalculate concurrency level for this
     * schedulre and return it.
     *
     * @EFFECTS return the concurrency level at this scheduler
     */
    public int getThisConcurrencyLevel() {
        return setChildConcurrencyLevel(null, 0);
    }
}
